#include "LZSS.h"
#include "Bitstream.h"
#include "Huffman.h"

#define MAX_LENGTH 1024 //max search length in buffer
#define DICT_SIZE 8 //dictionnary size of search
#define MIN_LENGTH_COMP 10 //min symbol size to compress


LZSS::LZSS(){}


void LZSS::compresse(char* source, char* destination)
{
  FILE * f=fopen(source,"r");
  fseek(f,0,SEEK_END);
  int size=ftell(f);
  //	int size=10000;//for fast debug
  fseek(f,0,SEEK_SET);
  unsigned char * buffer=new unsigned char[size];
  fread(buffer,size,1,f);
  fclose(f);
  
  //----------------------
  
  //compress
  unsigned char * pBuffer=new unsigned char[size*2];
  unsigned int LZSize;
  
  lzEncode(buffer,size,pBuffer,LZSize,true);

  FILE * fs = fopen(destination,"w");
  fwrite(pBuffer,1,LZSize,fs);
  fclose(fs);
  
  printf("input size : %i\n",size);
  printf("output size : %i\n",LZSize);
  printf("compression ratio : %.2f\n",size/(float)LZSize);
  
  
  //decompress
  unsigned int destSize;
  unsigned char * upBuffer=new unsigned char[size];
  
  lzDecode(pBuffer,upBuffer,destSize,true);

  //test
  int diff=memcmp(buffer,upBuffer,size);
  printf("differences : %i\n",diff);
  
  //----------------------
  
  delete[] pBuffer;
  delete[] buffer;
}

void LZSS::decompresse(char* source, char* destination)
{
  FILE * f=fopen(source,"r");
  fseek(f,0,SEEK_END);
  int size=ftell(f);
  //	int size=10000;//for fast debug
  fseek(f,0,SEEK_SET);
  unsigned char * pBuffer=new unsigned char[size];
  fread(pBuffer,size,1,f);
  fclose(f);


 //decompress
  unsigned int destSize=0;
  unsigned char * upBuffer=new unsigned char[size*100];

  lzDecode(pBuffer,upBuffer,destSize,true);
  
  FILE * fs = fopen(destination,"w");
  fwrite(upBuffer,1,destSize,fs);
  fclose(fs);
  //----------------------

  delete[] pBuffer;
  delete[] upBuffer;
}

//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

int LZSS::lzSave(unsigned char * source,int srcSize,unsigned char * & destination,bool compress)
{
  HuffmanPacker Packer;
  void * pBuffer;
  int bufferSize;

  if(compress)
    {
      Packer.Pack(source,srcSize);
      Packer.GetBuffer(&pBuffer,bufferSize);
    }
  else//no compression : only copy
    {
      bufferSize=srcSize;
      pBuffer=source;
    }

  //----------------------

  *(int*)destination=bufferSize;//save length buffer size
  destination+=4;
  memcpy(destination,pBuffer,bufferSize);
  destination+=bufferSize;

  return bufferSize+4; //+4 modified by JC
}

//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

void LZSS::lzEncode(unsigned char * source,unsigned int size,unsigned char * destination,unsigned int & destSize,bool useHuffman)
{
  unsigned char * position=source;
  unsigned char * end=source+size;
  unsigned char * dictionnary=source;

  int dictionnarySize=(1<<DICT_SIZE);//longer would take more bits to encode and more time to search
  int maxLength=MAX_LENGTH;//longer would take more bits to encode and be rare (could be split)

  std::vector<unsigned short> LZOffset;
  std::vector<unsigned char> LZLength;
  std::vector<unsigned char> LZSymbol;

  OutputBitStream select;
  select.Begin();
  WriteExpGolomb(size,select);

  //----------------------

  while(position<end)//scan all buffer
    {
      if ( ((position-source)*100/size) % 10 == 0 )
      	printf("\r%i%%",((position-source)*100)/size);

      //look for longest matching string
      int bestLength=0;
      int offset=0;
      //search backward to keep smallest offset
      for(unsigned char * search=position-1; search>dictionnary; search--)
	{
	  int length=0;
	  while(position+length<end //don't search after end of buffer (but you can search after actual position)
		&& length<maxLength-1 //limit string length for encoding efficiency
		&& search[length]==position[length])
	    length++;

	  if(length>bestLength)
	    {
	      bestLength=length;
	      offset=(int)(position-search);
	    }
	}

      //----------------------

      if(bestLength>=MIN_LENGTH_COMP)//encode string
	{
	  select.PushBit(1);
	  LZOffset.push_back(offset);
	  LZLength.push_back(bestLength);
	  position+=bestLength;
	}
      else//encode symbol
	{
	  select.PushBit(0);
	  LZSymbol.push_back(*position++);
	}
      dictionnary=std::max(source,position-dictionnarySize);//update ditionnary boundaries
    }
  printf("\r100%%\n");
  select.End();

  //----------------------

  //save offset (no compression)
  destSize=lzSave((unsigned char *)&LZOffset[0],(int)LZOffset.size()*2,destination,false);

  //save select
  destSize+=lzSave((unsigned char *)select.GetData(),select.GetDataSize(),destination,useHuffman);

  //save length
  destSize+=lzSave(&LZLength[0],(int)LZLength.size(),destination,useHuffman);

  //save symbol
  destSize+=lzSave(&LZSymbol[0],(int)LZSymbol.size(),destination,useHuffman);

  //----------------------
  
}

//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

void LZSS::lzRead(unsigned char * & source,unsigned char * & destination,bool compressed)
{
  int bufferSize=*(int*)source;
  source+=4;
  if(compressed)
    {
      HuffmanDepacker Depacker;
      Depacker.SetBuffer(source);
      int destBufferSize=Depacker.GetDepackSize();
      destination=new unsigned char[destBufferSize];
      Depacker.Depack(destination);
    }
  else
    {
      destination=new unsigned char[bufferSize];
      memcpy(destination,source,bufferSize);
    }
  source+=bufferSize;
}

//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------

void LZSS::lzDecode(unsigned char * source,unsigned char * destination,unsigned int & destSize,bool useHuffman)
{
  //read offset (uncompressed)
  unsigned char * LZOffset;
  lzRead(source,LZOffset,false);

  //read select
  unsigned char * LZSelect;
  lzRead(source,LZSelect,useHuffman);
  //select is a bitstream
  InputBitStream select;
  select.Begin((unsigned short *)LZSelect);
  ReadExpGolomb(select,destSize);

  //read length
  unsigned char * LZLength;
  lzRead(source,LZLength,useHuffman);

  //read symbol
  unsigned char * LZSymbol;
  lzRead(source,LZSymbol,useHuffman);

  //----------------------

  unsigned char * position=destination;
  unsigned char * end=destination+destSize;

  unsigned short * offset=(unsigned short *)LZOffset;
  unsigned char * length=LZLength;
  unsigned char * symbol=LZSymbol;

  //----------------------

  while(position<end)//scan all buffer
    {
      if(!select.Pop(1))//symbol
	*position++ = *symbol++;
      else//string
	{
	  int l=*length++;
	  for(int i=0;i<l;i++){
	    *position = *(position-(*offset));
	    position++;
	  }
	  offset++;
	}
    }
  
  //----------------------

  delete[] LZSelect;
  delete[] LZOffset;
  delete[] LZLength;
  delete[] LZSymbol;
}

LZSS::~LZSS(){}
